package algo.A05_其他排序算法;

import util.ArrayUtil;

public class M01_用数组表示树 {
    public static void main(String[] args) {
        int[] tree = ArrayUtil.getRandomArr(15, 0, 40);
        ArrayUtil.print(tree);

        System.out.print("先序遍历:");
        preOrder(tree, 0);
        System.out.println();
        System.out.print("中序遍历:");
        inOrder(tree, 0);
        System.out.println();
        System.out.print("后序遍历:");
        postOrder(tree, 0);
        System.out.println();
    }

    /**
     * 先序遍历
     *
     * @param arr   数组
     * @param index 访问的下标
     */
    private static void preOrder(int[] arr, int index) {
        //访问的下标不在树中时返回
        if (index >= arr.length) {
            return;
        }
        //输出根结点
        System.out.print(arr[index] + " ");
        //输出左子树
        preOrder(arr, 2 * index + 1);
        //输出右子树
        preOrder(arr, 2 * index + 2);
    }

    /**
     * 中序遍历
     *
     * @param arr
     * @param index
     */
    private static void inOrder(int[] arr, int index) {
        //访问的下标不在树中时返回
        if (index >= arr.length) {
            return;
        }
        //输出左子树
        inOrder(arr, 2 * index + 1);
        //输出根结点
        System.out.print(arr[index] + " ");
        //输出右子树
        inOrder(arr, 2 * index + 2);
    }

    /**
     * 后序遍历
     *
     * @param arr
     * @param index
     */
    private static void postOrder(int[] arr, int index) {
        //访问的下标不在树中时返回
        if (index >= arr.length) {
            return;
        }
        //输出左子树
        postOrder(arr, 2 * index + 1);
        //输出右子树
        postOrder(arr, 2 * index + 2);
        //输出根结点
        System.out.print(arr[index] + " ");
    }
}
